package P1线性结构.LeetCode单调栈与单调队列;

import java.util.ArrayDeque;
import java.util.LinkedList;

public class LC316 {
    public String removeDuplicateLetters(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        int[] count = new int[26];  //记录字母的次数
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            count[c - 'a']++;
        }
        boolean[] exits = new boolean[26];  //记录字母的存在性 默认false
        for (char c : s.toCharArray()) {
            count[c - 'a']--;
            if (exits[c - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && c < stack.peek()) {
                if (count[stack.peek() - 'a'] == 0) {
                    break;
                }
                exits[stack.pop() - 'a'] = false;
            }
            stack.push(c);
            exits[c - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}